Міністерство освіти і науки України Національний університет «Львівська політехніка» кафедра САПР
Лабораторна робота №4 з курсу "Чисельні методи в інформатиці" на тему: ЧИСЕЛЬНІ МЕТОДИ РОЗВ'ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ Виконав: cт. гр. КН-316 Прийняв: Львів-2008 1. МЕТА РОБОТИ Мета роботи – ознайомитись із чисельними методами розв'язування систем лінійних алгебраїчних рівнянь та їх практичним застосуванням. 2. ТЕОРЕТИЧНА ЧАСТИНА Методи розв'язування систем лінійних рівнянь можна поділити на два типи: прямі, або точні, та ітераційні. Прямі методи дають можливість дістати розв'язок, виконавши скінченну апріорі відому кількість операцій. Якщо всі проміжні обчислення виконувати точно (без заокруглень), то отримаємо точний розв'язок. Ітераційні методи дають нескінченну послідовність наближених розв'язків, границі яких є розв'язком системи. 2.1. Прямі методи розв'язування систем лінійних алгебраїчних рівнянь Із точних методів розв'язування систем лінійних рівнянь відомий з курсу лінійної алгебри метод Гаусса, реалізація якого за схемою єдиного ділення вимагає виконання n(4n2-3n-4)/6 арифметичних операцій. Розглянемо розв'язування систем лінійних рівнянь методом Гаусса за схемою Халецького, для реалізації якої необхідно n(2n-1) арифметичних операцій. Система лінійних алгебраїчних рівнянь в матричному представленні має вигляд:
(1) Матрицю коефіцієнтів А подаємо у вигляді добутку двох трикутних матриць, тобто: А=СВ. (2) Матриця С – нижня трикутна, В – верхня трикутна, причому діагональні коефіцієнти матриці В дорівнюють одиниці. Підставимо (2) в (1): CBx=d. (3) Позначимо Bx=y і перепишемо (3) у вигляді: Cy=d (4) Розв'язок (4) називається прямим ходом методу Гаусса, розв'язок (3) – зворотним ходом. Отже, першим кроком при розв'язуванні сформульованої задачі є розбиття матриці А на дві трикутні матриці С і В. Коефіцієнти матриць С і В обчислюються послідовно. Спочатку обчислюється перший стовпець матриці С:
, тоді обчислюється перший рядок матриці В:
і елемент
, після чого – елементи другого стовпця матриці С:
тоді обчислюються елементи другого рядка матриці В:
і елемент:
і т.д. Після того, як будуть обчислені елементи матриць С і В, а також вектор y, знаходять невідомі
:

. Алгоритм методу Гаусса за схемою Халецького має такий компактний вигляд:




2.2.1. Метод простої ітерації Найпростішим ітераційним методом розв'язування систем лінійних рівнянь ах=d (5) є метод простої ітерації. Система рівнянь (5) перетворюється до вигляду: x=вx+e, (6) де
,
. (7) Ітераційний процес записується у вигляді:

. (8) Для збіжності методу простих ітерацій при довільному початковому наближенні
ітераційного процесу (8) необхідно і достатньо, щоб всі власні значення матриці B були за модулем менші від одиниці. Обчислювальна схема методу простої ітерації: 1. Обчислюємо елементи матриці B і вектора e за (7). 2. Обчислюємо
. Позначаємо:
,
. Якщо C<1, то ітераційний процес збігається. 3. Як початкове наближення
вибираємо вектор e:
=e. Позначимо
. Розв'язуємо систему рівнянь:
. Тоді:
. 4. Обчислюємо необхідну кількість ітерацій для досягнення потрібної точності
розв'язку:
. Звідси

. (9) 2.2.2. Метод Зейделя Ітераційний метод Зейделя відрізняється від методу простої ітерації тим, що на (k+1)-й ітерації при обчисленні і-ї компоненти вектора
використовуються значення
, обчислені на цій ітерації. Обчислювальна схема методу Зейделя: Для реалізації методу Зейделя необхідно: 1. Перевірити достатню умову збіжності:
. ...